Title: Haskell Magic: From semigroup to Foldable
Date: 2018-09-24
Modified: 2018-09-26
Category: Blog
Slug: haskell-magic-from-semigroup-to-foldable
Tags: haskell-magic, haskell
Summary: Where I talk about how I figured out why foldMap matters

Anyone who's been working with Haskell for a little while will encounter
``Foldable`` pretty quickly. This typeclass not only contains a range of
useful operations, it is defined on a _lot_ of different data types. However,
every time I looked at the minimal required definition for a ``Foldable``
instance, I was always a bit
puzzled. Essentially, you have the option of implementing one of either

    :::haskell
    foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

or

    :::haskell
    foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m

While I had no issue understanding how everything provided by ``Foldable`` could
be implemented based on ``foldr``, I simply could not see how the same could be
done with ``foldMap``. I never gave it much thought until recently, when, on a
whim, I decided to dig into this question. What I ended up discovering was
both interesting and insightful, and I figured I'd share my thought process, as
well as discoveries, with the world. So, here goes.

## The smart semigroup, the marvelous monoid ##

Before we can discuss anything about ``Foldable`` or ``foldMap``, we need to lay
a few foundations. One such foundation is the _semigroup_, which is a structure
that is both incredibly simple and common in mathematics. You can hardly go
two steps into _any_ mathematical discipline without seeing a semigroup, in
fact. Intuitively, a semigroup is a set _S_ with an associative binary operator · _: (S, S) →
S_ (that is, for any _x, y, z_ in _S_, it should be the case that _((x_ · _y)_ · _z)
= (x_ · _(y _·_ z))_). Because of this associativity, we don't usually bother
bracketing ·. In Haskell, we have an analogous type class, with appropriate
laws, as follows:

    :::haskell
    class Semigroup a where
      (<>) :: a -> a -> a

    -- Such that ((x <> y) <> z) == (x <> (y <> z))

We can extend this idea further by adding a _unit element_ which does not change
anything when combined with _·_. In Haskell:

    :::haskell
    class (Semigroup m) => Monoid m where
      mempty :: a

    -- Such that mempty <> x == x <> mempty == x

Now, this doesn't seem like much - I've had at least one person tell me that
they don't see what the big deal about monoids is - but this simple idea is
surprisingly powerful. It wouldn't be an exaggeration to say that many of the
most critical parts of Haskell rely on monoids: for instance, both
[``Applicative``][1] and [``Monad``][2] critically rely on the ideas behind monoids. 
In our case, though, it turns out that monoids also enable ``Foldable``, which is why we need them
around.

Just as with semigroups, monoids are _everywhere_; let's consider some notable
ones. For starters, even something as simple as ``Bool`` can be a monoid - in
two different ways! To distinguish between these (and help GHC understand which
one we want), we define newtypes like so:

    :::haskell
    newtype Any = Any { getAny :: Bool }

    instance Semigroup Any where
      (Any x) <> (Any y) = Any (x || y)

    instance Monoid Any where
      mempty = False

    newtype All = All { getAll :: Bool }

    instance Semigroup All where
      (All x) <> (All y) = All (x && y)

    instance Monoid All where
      mempty = True

Similarly, ``Int`` is also a monoid in two ways:

    :::haskell
    newtype Sum = Sum { getSum :: Int }

    instance Semigroup Sum where
      (Sum x) <> (Sum y) = Sum (x + y)

    instance Monoid Sum where
      mempty = 0

    newtype Product = Product { getProduct :: Int }

    instance Semigroup Product where
      (Product x) <> (Product y) = Product (x * y)

    instance Monoid Product where
      mempty = 1

These are unsurprising and natural instances for which the respective laws are
easy to verify. Another common and useful monoid is ``[a]`` for _any_ ``a``:

    :::haskell
    instance Semigroup [a] where
      x <> y = x ++ y

    instance Monoid [a] where
      mempty = []

``[a]`` is actually quite special as far as monoids are concerned, as it enables
us to turn absolutely anything into a monoid; to use fancier language, ``[a]``
is the [_free monoid_][3]. Similarly, anything 'list-shaped' (such as
``Vector``) can also be made into a monoid in a similar way. 

We can also get more exotic monoids. Consider this (also important)
example:

    :::haskell
    newtype Endo a = Endo { appEndo :: a -> a }

    instance Semigroup (Endo a) where
      (Endo f) <> (Endo g) = Endo (f . g)

    instance Monoid (Endo a) where
      mempty = Endo id

This is the monoid for _endomorphisms_, which are functions from values to
values in the same type. 

## What's the point of these? ##

The commonality of monoids isn't their only notable features; they also define a
way of 'folding'. Suppose we had a list of monoidal values, and we wanted to
'squash' it into a single value. Thanks to those values being in some monoid, we
can do this operation no matter how many of them we have. To demonstrate, we
have the following function:

    :::haskell
    mconcat :: (Monoid m) => [m] -> m
    mconcat [] = mempty
    mconcat (x : xs) = x <> mconcat xs

We have an ``mconcat`` for any ``Monoid`` whatsoever, although some monoids
might be able to define this more efficiently. Additionally, because of the
associativity of ``<>``, we can perform ``mconcat`` in parallel by reassociating
the uses of ``<>`` to look like a balanced binary tree instead of a list. For
instance, if we had the following 2D list:

    :::haskell
    twoDee :: [[Int]]
    twoDee = [[1, 2, 3], [4, 5], [6, 7, 8]]

the default ``mconcat`` would 'flatten' them as so:

    :::haskell
    slowFlatten :: [Int]
    slowFlatten = [1, 2, 3] <> ([4, 5] <> ([6, 7, 8] <> []))

but thanks to associativity, we can instead do:

    :::haskell
    fastFlatten :: [Int]
    fastFlatten = ([1, 2, 3] <> [4, 5]) <> ([6, 7, 8] <> [])

The savings between these can be substantial, especially if ``<>`` takes worse
than _O(1)_ time. More specifically, for any linear ``<>``, performing the
default ``mconcat`` on a list of length _n_ full of monoidal values of 'length'
_k_ requires _O(n²k)_ time, but by doing a reassocation similar to
``fastFlatten``, we can bring this down to _O(n log(n)k)_. 

"Surely this isn't enough for us to define ``Foldable`` though?", I immediately
hear you ask. You'd be right to think so, given the power and generality of
``foldr`` as a method. However, surprisingly, it _is_ enough, and we're about to
find out how.

## Look Ma, no laws ##

Consider the following (considerably reduced) definition of ``Foldable``:

    :::haskell
    class Foldable t where
      foldMap :: Monoid m => (a -> m) -> t a -> m

No, it's not a typo - there aren't any laws on this one. To quote the [Haskell
Wikibook][4], ``Foldable`` is both principled and general-purpose like that.
There are definitely some expectations of what a sensible ``foldMap`` should do
- it shouldn't 'skip' any values, for example - but we can't really pin any laws
  on it the same way we can for, say, ``Functor``. 

Let's think, intuitively, what ``foldMap`` says to us it can do. If we give a
way of projecting ``a``s into monoidal ``m``s, ``foldMap`` will do this for
every ``a`` 'in' our ``Foldable``, and then smush them all together similarly to
``mconcat`` above. An example of a (sensible) instance for ``[]`` would be:

    :::haskell
    instance Foldable [a] where
      foldMap f = mconcat . fmap f

The interesting thing about ``foldMap`` is that we can gain a massive diversity
of behaviour by simply varying which ``Monoid`` we project our values into.
Let's try a few, starting with the two different ``Monoid`` instances for
(wrapped) ``Bool``s, with which we can recover these functions:

    :::haskell
    any :: Foldable t => (a -> Bool) -> t a -> Bool
    any p = getAny . foldMap (Any . p)

    all :: Foldable t => (a -> Bool) -> t a -> Bool
    all p = getAll . foldMap (All . p)

We'll be seeing this 'project, wrap, ``foldMap``, unwrap' pattern a lot in the
rest of this post. Additionally, we can recover another useful function
with a slight adjustment:

    :::haskell
    elem :: (Foldable t, Eq a) => a -> t a -> Bool
    elem x = getAny . foldMap (Any . (==) x)

This is the first true sign of the power of ``foldMap``. At a glance, ``elem``
has nothing to do with monoids or ``foldMap``, yet the definition above
demonstrates not only that these concepts are connected, but that we can define
``elem`` using only ``foldMap`` with an appropriate monoid. 

So, ``Bool`` is getting a bit boring now; let's try ``Int`` instead. Defining
``sum`` and ``product`` is too easy (but worth doing for practice), so let's
observe something more interesting:

    :::haskell
    length :: Foldable t => t a -> Int
    length = getSum . foldMap (Sum . const 1)

    count :: Foldable t => (a -> Bool) -> t a -> Bool
    count p = getSum . foldMap (Sum . fromEnum . p)

Admittedly the second one is cheating a bit, as it takes advantage of the fact
that ``fromEnum False = 0`` and ``fromEnum True = 1``, but at the same time, we
again show the power of ``foldMap`` to define seemingly extremely unrelated
concepts. ``count`` is especially clever, because it combines ``any`` and
``length`` in a clever way. Unfortunately for us, ``base`` doesn't provide
``count`` just yet (surprisingly).

Now I want to show probably the single coolest aspect of all this investigation
(at least for me) - what we can define if we use ``[]`` as our monoid:

    :::haskell
    toList :: Foldable t => t a -> [a]
    toList = foldMap pure

The sheer _elegance_ of this definition amazes me - it's like all the pieces
were invented the way they were just to make this work:

  1. ``pure`` for lists defaults to creating a singleton list.
  1. ``foldMap`` turns everything in an arbitrary ``Foldable`` into some
     ``Monoid``, then smushes them all together.
  1. This gives a demonstration of the essence of ``Foldable``ness, in a similar
     way to the way [the Typeclassopedia][5] describes it.

I have to state, for the record, that this definition of ``toList`` is
_definitely_ not efficient for almost any ``Foldable`` - we can usually define
a ``toList`` that runs in _O(n)_ for almost any ``Foldable``, but this one will
be _O(n²)_ (at worst) or _O(n log(n))_ (at best). However, the elegance of this
definition is still amazing.

## The real heart of the problem ##

We can continue playing with our ``Foldable`` and different instances of
``Monoid`` for quite a while, and define some interesting and useful
functions in the process. However, ultimately, what we want is to show just how
something like ``foldr`` can be defined in terms of ``foldMap``. It seems we
need a truly special monoid to achieve this - and it happens to be ``Endo``.

Now, suppose that, for some reason, we couldn't just look up ``Data.Foldable``,
and only had the above information to go on. Our goal is to define ``foldr``,
which we remind ourselves is:

    :::haskell
    foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

Let's give it a whirl using our well-established pattern:

    :::haskell
    :t appEndo . foldMap (Endo . _)

    -- Found hole: _ :: a -> b -> b

Hmm, we just happen to have something like that lying around: the first
argument to ``foldr``. So if we substitute that in and continue:

    :::haskell
    :t \f -> appEndo . foldMap (Endo . f)
    
    -- Types as: Foldable t => (a -> b -> b) -> t a -> b -> b

This is really close to what we want, a bit of argument wrangling aside. At this
stage, it's worth asking what exactly this is doing. Let's consider what happens
when we provide a suitable function and ``Foldable`` instance to the skeleton
above:

    :::haskell
    :t (\f -> appEndo . foldMap (Endo . f)) (+) [1,2,3,4]

    -- Types as: Num a => a -> a

Ah, so our version of ``foldr`` essentially _cooks us a custom function_ to
transform some value into some other value of the same type (or, to use our
already-established vocabulary, it cooks us a custom endomorphism). It does this 
'cooking' as follows:

  1. We provide a ``Foldable`` full of ``a``s.
  1. ``foldMap`` 'maps' ``f`` over all of them, currying in each of those ``a``s
     as the first argument, then wraps each one up in an ``Endo b`` (which, as
     we know, is nothing other than a wrapper for ``b -> b``).
  1. ``foldMap`` then smushes all of these ``Endo b``s together (essentially
     composing them all) into one big ``Endo``, representing every 'stage' of
     this computation all in one go.
  1. Lastly, we unwrap the resulting ``Endo`` to get our ``b -> b``.

We now have a way of transforming any 'starting value' into whatever result
would arise based on accumulating that starting value through multiple
applications of ``f``, using each ``a`` in our ``Foldable``. Given that we
specify _nothing_ about ``b`` as part of the definition of ``foldr``, we can, by
definition, have this do anything that involves accumulation - which, as it
turns out, is [basically anything ever][6]. Once again, the power of monoids and
``foldMap`` shows itself, and we now know why ``foldMap`` is enough.

## Rounding out the fun ##

Just because we can, let's now consider how we can define ``foldMap`` with
``foldr``, just to show that they are equivalent in power. Let's again imagine,
for a second, that we couldn't just look up ``Data.Foldable``. We have to go
from this:

    :::haskell
    foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

to this:

    :::haskell
    foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m

Given that ``foldr`` needs a 'starting value', let's try and figure that out
first. We observe that this 'starting value' (typed ``b`` above) has to be the
same as the final result. Given that we expect an ``m`` from ``foldMap``, it
means our 'starting value' has to be an ``m`` too. Additionally, this ``m`` is
not provided - we have to be able to 'magic it up' _regardless of what monoid we
need_. Clearly, only one thing fits: ``mempty``. Let's
see what this gives us:

    :::haskell
    :t \f t -> foldr f mempty t
    -- Types as: (Foldable t, Monoid m) => (a -> m -> m) -> t a -> m

Close, but not quite - the signature for ``foldMap`` provides us a
function of the type ``a -> m``, but _not_ ``a -> m -> m``. We do, however, for
anything that's an instance of ``Monoid``, have a function of type ``m -> m -> m``:
``(<>)``. Filling that in, we get this:

    :::haskell
    :t \f t -> foldr ((<>) . f) mempty t
    -- Types as: (Foldable t, Monoid m) => (a -> m) -> t a -> m

Perfect! We have now closed the circle and demonstrated definitively that
``foldMap`` and ``foldr`` are equally powerful (if not necessarily efficient).

## Wrapping up ##

Sorry, I couldn't resist that one. This foray into ``Foldable`` yielded me some
interesting insights, which I hope will be useful for others. It once again
reminds me how powerful good, law-abiding primitives, a little logic and
creativity, and, of course, the power of Haskell, can be. Having read this, you
can now better use ``Foldable`` [in anger][7], understand why monoids
are amazing, and had a fun time discovering something new (or at least, I did
all the above; your mileage may vary).

For those who want to know more, I recommend [mastering foldr][8] by [the late
Ertugrul Söylemez][9] (whose loss to the Haskell community is as major as it was
sudden). If you enjoyed this sort of 'discovery post', I also recommend the
following, which follow a similar approach:

  * [The Const Applicative and Monoids][10]
  * [The Essence of the Iterator Pattern][11]
  * [Lenses embody Products, Prisms embody Sums][12]
  * [Free Lenses for Higher-Kinded Data][13]
  * [You Could Have Invented Matrices!][14]

Think hard and have fun, always.

[1]: http://blog.ezyang.com/2012/08/applicative-functors
[2]: https://bartoszmilewski.com/2016/12/27/monads-categorically
[3]: https://bartoszmilewski.com/2015/07/21/free-monoids
[4]: https://en.m.wikibooks.org/wiki/Haskell/Foldable#More_facts_about_Foldable
[5]: https://wiki.haskell.org/Typeclassopedia#Foldable_actually_isn.27t
[6]: http://www.cs.nott.ac.uk/~pszgmh/fold.pdf
[7]: https://english.stackexchange.com/questions/30939/is-used-in-anger-a-britishism-for-something
[8]: http://ertes.eu/tutorial/foldr.html
[9]: https://blog.jle.im/entry/in-memory-of-ertugrul-soylemez.html
[10]: https://blog.jle.im/entry/const-applicative-and-monoids.html
[11]: https://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf
[12]: https://blog.jle.im/entry/lenses-products-prisms-sums.html
[13]: http://reasonablypolymorphic.com/blog/free-lenses
[14]: https://blog.jle.im/entry/you-could-have-invented-matrices.html
